Graphe dual

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Pour les articles homonymes, voir Dualité (mathématiques) pour les autres notions de dualité en mathématiques.

En théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ.

Cette notion généralise celle de dualité dans les polyèdres.

Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan.

Un graphe (plongé) isomorphe à son dual est dit autodual.